package codeRandomThoughts.Test99901背包;

/**
 * 用一个一维数组记录动态规划的结果
 * 从后往前遍历的根本原因:每次更新数值都要用到左边和上边的值,我们要保证左边的值仍然是上一层的
 * 从右往左,可以先更新右侧的,这样右侧一直用的是上一层的左侧值,最后再更新左侧,这样就不会冲突
 */
public class Solution2 {
    public static int testWeightBagProblem(int[] weight, int[] value, int bagSize) {
        //dp数组
        int[] dp = new int[bagSize + 1];

        //初始化 就是i=0的情况
        for (int j = weight[0]; j <= bagSize; j++) {
            dp[j] = value[0];
        }

        //开始递推
        for (int i = 1; i < weight.length; i++) {
            for (int j = bagSize; j >= 0; j--) {//这里要从后往前遍历,不然更新后的结果会影响到其他值
                //如果当前容量不够装下当前的物品
                if (j < weight[i]) {
                    //这里可以写到for循环条件里面
//                    dp[j]=dp[j];
                } else {
                    dp[j] = Integer.max(dp[j], dp[j - weight[i]] + value[i]);
                }
            }
        }

        return dp[bagSize];
    }

    public static void main(String[] args) {
        int[] weight = {1, 3, 4};
        int[] value = {15, 20, 30};
        int bagSize = 4;
        System.out.println(testWeightBagProblem(weight, value, bagSize));
    }
}
